package com.example.algorithm.no0003.solution;

import com.example.algorithm.no0003.Solution;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @Description 解答-无重复字符的最长子串-queue解法
 * @ClassName QueueSolution
 * @Author Administrator
 * @Date 2020/5/20 10:26
 * @Version 1.0.0
 */
public class QueueSolution implements Solution {
    @Override
    public int lengthOfLongestSubstring(String s) {
        if (s.length() <= 1) {
            return s.length();
        }

        int maxLength = 0;
        int lIndex = 0;
        int rIndex = 1;

        // 使用队列保存当前的最长不重复子串
        Deque<Character> deque = new LinkedList<>();
        deque.add(s.charAt(lIndex));

        while (lIndex <= rIndex && rIndex < s.length()) {
            if (deque.contains(s.charAt(rIndex))) {
                lIndex++;
                deque.poll();
                continue;
            }
            deque.offer(s.charAt(rIndex));
            maxLength = Math.max(maxLength, deque.size());
            rIndex++;
        }
        return maxLength;
    }
}
